package 经典例题;

import java.util.List;

public class 汉诺塔问题 {

    //解题思路
//    n = 1 时，直接把盘子从 A 移到 C；
//n > 1 时，
//
//    先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
//    再将最大的盘子从 A 移到 C；
//    再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
         mov(A.size(),A,B,C);
    }

    private void mov(int size, List<Integer> a, List<Integer> b, List<Integer> c) {
        if (size==1){
            c.add(a.remove(a.size()-1));
            return;
        }
        //    先把上面 n - 1 个盘子从 A 移到 B（子问题，递归）；
        mov(size-1,a,c,b);
        //    再将最大的盘子从 A 移到 C；
        c.add(a.remove(a.size()-1));
        //    再将 B 上 n - 1 个盘子从 B 移到 C（子问题，递归）。
        mov(size-1,b,a,c);
    }
}
